<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Total unimodulare Matrix</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Total_unimodulare_Matrix"> <link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Total_unimodulare_Matrix rootpage-Total_unimodulare_Matrix skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Total unimodulare Matrix</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Eine <b>total unimodulare Matrix</b> (oder auch <b>vollständig unimodulare Matrix</b>) ist eine <a href="Matrix_(Mathematik)" title="Matrix (Mathematik)">Matrix</a> mit <a href="Ganzzahlig" class="mw-redirect" title="Ganzzahlig">ganzzahligen</a> Einträgen, bei der noch weitere Forderungen an deren <a href="Unterdeterminante" class="mw-redirect" title="Unterdeterminante">Unterdeterminanten</a> gestellt sind. Total unimodulare Matrizen spielen in der <a href="Diskrete_Optimierung" class="mw-redirect" title="Diskrete Optimierung">diskreten Optimierung</a> eine Rolle, da sie unter bestimmten Bedingungen die Ganzzahligkeit der Lösung eines <a href="Lineare_Optimierung" title="Lineare Optimierung">linearen Optimierungsproblems</a> garantieren.
</p>
<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>
<p>Sei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\in \mathbb {R} ^{n\times m}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>×<!-- × --></mo>
<mi>m</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A\in \mathbb {R} ^{n\times m}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ad600f721776272549faed3bdcaa4b647e8cc3ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle A\in \mathbb {R} ^{n\times m}}" loading="lazy"></span> eine Matrix. Dann heißt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> total unimodular (manchmal auch absolut unimodular oder vollständig unimodular) genau dann, wenn jede Unterdeterminante von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> einen der Werte <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo>−<!-- − --></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle -1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/704fb0427140d054dd267925495e78164fee9aac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.971ex; height:2.343ex;" alt="{\displaystyle -1}" loading="lazy"></span> oder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>0</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span> oder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></span> hat.
Insbesondere sind dann alle <a href="Matrix_(Mathematik)" title="Matrix (Mathematik)">Elemente</a> (also alle <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\times 1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
<mo>×<!-- × --></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1\times 1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b4bf91a527dc01af9ef6ace81199becf1308e00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 1\times 1}" loading="lazy"></span>-Untermatrizen) von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\in \mathbb {R} ^{n\times m}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>×<!-- × --></mo>
<mi>m</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A\in \mathbb {R} ^{n\times m}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ad600f721776272549faed3bdcaa4b647e8cc3ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle A\in \mathbb {R} ^{n\times m}}" loading="lazy"></span> in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,0,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">{</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \{-1,0,1\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bfea59344fba4be112907c8cce96d32caa794a84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.688ex; height:2.843ex;" alt="{\displaystyle \{-1,0,1\}}" loading="lazy"></span>.
</p><p>Alternativ formuliert ist eine total unimodulare Matrix eine (nicht notwendigerweise quadratische) Matrix, bei der alle quadratischen, nichtsingulären Untermatrizen <a href="Ganzzahlige_unimodulare_Matrix" title="Ganzzahlige unimodulare Matrix">ganzzahlig unimodular</a> sind.
</p>
<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>
<ul><li>Die <a href="Inzidenzmatrix" title="Inzidenzmatrix">Inzidenzmatrix</a> eines ungerichteten <a href="Bipartiter_Graph" title="Bipartiter Graph">bipartiten Graphen</a> ist total unimodular.</li>
<li>Die <a href="Inzidenzmatrix" title="Inzidenzmatrix">Inzidenzmatrix</a> eines <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteten Graphen</a> ist total unimodular.</li>
<li>Ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> total unimodular, so ist auch die <a href="Transponierte_Matrix" title="Transponierte Matrix">transponierte Matrix</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{T}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>T</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A^{T}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d978c0c4f22282a313e4107f97b9eda56315b258.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.132ex; height:2.676ex;" alt="{\displaystyle A^{T}}" loading="lazy"></span> total unimodular, denn Determinanten bleiben unter Transposition erhalten.</li>
<li>Ihre Bedeutung bekommen total unimodulare Matrizen aufgrund der folgenden Aussage: Ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> total unimodular und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\in \mathbb {Z} ^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>b</mi>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle b\in \mathbb {Z} ^{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1474009777c0d3c9ceebe90ab432195163f987c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.607ex; height:2.343ex;" alt="{\displaystyle b\in \mathbb {Z} ^{n}}" loading="lazy"></span>, so besitzt das <a href="Polyeder" title="Polyeder">Polyeder</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\{x\,|\,Ax\leq b\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>P</mi>
<mo>=</mo>
<mo fence="false" stretchy="false">{</mo>
<mi>x</mi>
<mspace width="thinmathspace"></mspace>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mspace width="thinmathspace"></mspace>
<mi>A</mi>
<mi>x</mi>
<mo>≤<!-- ≤ --></mo>
<mi>b</mi>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle P=\{x\,|\,Ax\leq b\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/773eb4246527f4cfac3c97cb01156fc0c65d150f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.088ex; height:2.843ex;" alt="{\displaystyle P=\{x\,|\,Ax\leq b\}}" loading="lazy"></span> nur ganzzahlige Ecken. Ist ein lineares Optimierungsproblem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \min c^{T}x}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo movablelimits="true" form="prefix">min</mo>
<msup>
<mi>c</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>T</mi>
</mrow>
</msup>
<mi>x</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \min c^{T}x}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4751a2abbe9d7e685adc8a7b661c9ab696050ab3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.988ex; height:2.676ex;" alt="{\displaystyle \min c^{T}x}" loading="lazy"></span> unter der Nebenbedingung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in P}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>x</mi>
<mo>∈<!-- ∈ --></mo>
<mi>P</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x\in P}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7cc98d5d7d5ae8afe28ea054450cac2af7bca3d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.916ex; height:2.176ex;" alt="{\displaystyle x\in P}" loading="lazy"></span> gegeben, so ist die Optimallösung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span> ganzzahlig. Ist außerdem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in \mathbb {Z} ^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>c</mi>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle c\in \mathbb {Z} ^{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3ce3d1294d4f58073658a93dfcff75c3957bbf1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.616ex; height:2.343ex;" alt="{\displaystyle c\in \mathbb {Z} ^{n}}" loading="lazy"></span>, so ist auch der Zielfunktionswert <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{T}x^{*}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>c</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>T</mi>
</mrow>
</msup>
<msup>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle c^{T}x^{*}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/64d0efa1e014393743ab2486aac13cd4d91ee408.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.78ex; height:2.676ex;" alt="{\displaystyle c^{T}x^{*}}" loading="lazy"></span> ganzzahlig.</li>
<li>Die Anzahl an Untermatrizen einer Matrix ist exponentiell in der Anzahl der Zeilen/Spalten der Matrix. Obwohl alle diese Untermatrizen zur Charakterisierung der totalen Unimodularität herangezogen werden, gibt es einen polynomiellen Algorithmus zur Entscheidung, ob eine Matrix total unimodular ist oder nicht.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>
<p>Betrachte die Matrix
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A:={\begin{pmatrix}1&1&0&0\\0&0&1&1\\1&0&1&0\end{pmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
<mo>:=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>(</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>)</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A:={\begin{pmatrix}1&1&0&0\\0&0&1&1\\1&0&1&0\end{pmatrix}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/37ba3d885d7c9738ab633f4cf2017185a9708b6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:21.924ex; height:9.176ex;" alt="{\displaystyle A:={\begin{pmatrix}1&1&0&0\\0&0&1&1\\1&0&1&0\end{pmatrix}}}" loading="lazy"></span></dd></dl>
<ol><li>Alle Einträge sind entweder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>0</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span> oder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></span> und damit auch alle <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\times 1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
<mo>×<!-- × --></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1\times 1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b4bf91a527dc01af9ef6ace81199becf1308e00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 1\times 1}" loading="lazy"></span>-Untermatrizen</li>
<li>Enthält eine <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\times 2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mo>×<!-- × --></mo>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2\times 2}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f8a0e3400ffb97d67c00267ed50cddfe824cbe80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 2\times 2}" loading="lazy"></span> Matrix nur Einträge aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,0,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">{</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \{-1,0,1\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bfea59344fba4be112907c8cce96d32caa794a84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.688ex; height:2.843ex;" alt="{\displaystyle \{-1,0,1\}}" loading="lazy"></span> und dabei mindestens eine Null, so ist ihre Determinante auch aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,0,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">{</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \{-1,0,1\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bfea59344fba4be112907c8cce96d32caa794a84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.688ex; height:2.843ex;" alt="{\displaystyle \{-1,0,1\}}" loading="lazy"></span>. Insbesondere sind die Determinanten aller <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\times 2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mo>×<!-- × --></mo>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2\times 2}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f8a0e3400ffb97d67c00267ed50cddfe824cbe80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 2\times 2}" loading="lazy"></span>-Untermatrizen der obigen Matrix aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,0,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">{</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \{-1,0,1\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bfea59344fba4be112907c8cce96d32caa794a84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.688ex; height:2.843ex;" alt="{\displaystyle \{-1,0,1\}}" loading="lazy"></span>.</li>
<li>Mittels der <a href="Regel_von_Sarrus" title="Regel von Sarrus">Regel von Sarrus</a> kann man überprüfen, dass auch die Determinanten der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3\times 3}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>3</mn>
<mo>×<!-- × --></mo>
<mn>3</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 3\times 3}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ddc0d4d6106875f8006be1d898512ca5843bad8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 3\times 3}" loading="lazy"></span>-Untermatrizen aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,0,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">{</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \{-1,0,1\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bfea59344fba4be112907c8cce96d32caa794a84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.688ex; height:2.843ex;" alt="{\displaystyle \{-1,0,1\}}" loading="lazy"></span> sind.</li></ol>
<p>Daher ist die Matrix total unimodular.
</p>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li><a href="Martin_Aigner" title="Martin Aigner">Martin Aigner</a>: <cite style="font-style:italic">Diskrete Mathematik</cite> (= <cite style="font-style:italic">Vieweg Studium: Aufbaukurs Mathematik</cite>). 6., korrigierte Auflage. <a href="Vieweg" class="mw-disambig" title="Vieweg">Vieweg</a>, Wiesbaden 2006, ISBN 978-3-8348-0084-8.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Total+unimodulare+Matrix&rft.au=Martin+Aigner&rft.btitle=Diskrete+Mathematik&rft.date=2006&rft.edition=6.%2C+korrigierte&rft.genre=book&rft.isbn=9783834800848&rft.place=Wiesbaden&rft.pub=Vieweg&rft.series=Vieweg+Studium%3A+Aufbaukurs+Mathematik" style="display:none"> </span></li>
<li><a href="Bernhard_Korte" title="Bernhard Korte">Bernhard Korte</a>, <a href="Jens_Vygen" title="Jens Vygen">Jens Vygen</a>: <cite style="font-style:italic">Kombinatorische Optimierung: Theorie und Algorithmen</cite>. 3. Auflage. <a href="Springer_Spektrum" title="Springer Spektrum">Springer Spektrum</a>, Berlin 2018, ISBN 978-3-662-57690-8, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>122<span style="display:inline-block;width:.2em"> </span>ff</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Total+unimodulare+Matrix&rft.au=Bernhard+Korte%2C+Jens+Vygen&rft.btitle=Kombinatorische+Optimierung%3A+Theorie+und+Algorithmen&rft.date=2018&rft.edition=3.&rft.genre=book&rft.isbn=9783662576908&rft.pages=122+ff.&rft.place=Berlin&rft.pub=Springer+Spektrum" style="display:none"> </span></li>
<li><a href="Alexander_Schrijver" title="Alexander Schrijver">Alexander Schrijver</a>: <cite style="font-style:italic">Combinatorial optimization</cite>. Polyhedra and efficiency. Springer, Berlin 2003, ISBN 978-3-540-44389-6 (3 Bände, 1881 Seiten).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Total+unimodulare+Matrix&rft.au=Alexander+Schrijver&rft.btitle=Combinatorial+optimization&rft.date=2003&rft.genre=book&rft.isbn=9783540443896&rft.place=Berlin&rft.pub=Springer" style="display:none"> </span></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2021-04-03" href="https://de.wikipedia.org/wiki/?title=Total_unimodulare_Matrix&oldid=210510914">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>